package digui;

import java.util.Arrays;

public class _09超过一半的数字 {
    //数组中出现次数超过半数的元素
    //解法1：排序后返回arr[N/2],NLg(N)
    //解法2：hash统计
    //解法3：顺序统计,O(N)，限制：需要改动数组的内容
    //解法4：不同的数，进行消除 (见寻找发帖王）

    public static void main(String[] args) {
        int[] a = {1,2,1,1};
        solve1(a);
        solve3(a);
    }
    public static void solve1(int[] a){
        Arrays.sort(a);
        System.out.println(a[a.length/2]);
    }

    public static void solve3(int[] a){
        int res = _08第K个元素.selectK(a, 0, a.length - 1, a.length / 2);
        System.out.println(res);
    }
}
